This invention relates generally to communication systems and, more particularly, to a system and method for efficiently transmitting and receiving messages in a multiple access communications network without collisions.
In communication systems, a channel, defined as a bandwidth of frequency in a frequency division system or a time slot in a time division system, is considered a fixed communication resource. To improve communication efficiencies, several remote units in the system must typically share the fixed resource. That is, the remote units must all use the same channel. The term multiple access refers to the sharing of a fixed communication resource. Multiple Access Control (MAC) protocols can be divided into two broad categories—fixed assignment and random access. Random access protocols can be further divided into pure random access and controlled random access.
Fixed assignment MAC protocols are typically used when a continuous stream of data is to be transmitted. Examples of such data are digitized voice traffic, video transmission and facsimile transmission. The most common fixed assignment methods include Frequency Division Multiple Access (FDMA), in which sub-bands of frequency are specified; Time Division Multiple Access (TDMA), in which periodic time slots are specified; and Code Division Multiple Access (CDMA), in which a set of orthogonal spread spectrum codes are specified.
If the information is to be transmitted as intermittent or bursty data messages, fixed assignment methods can result in communication resources being wasted much of the time. Random access MAC protocols provide a more flexible and efficient way of managing channel access for communication of short data messages. Commonly used random access schemes include the pure ALOHA protocol, the slotted-ALOHA protocol, Carrier Sense Multiple Access with Collision Detection (CSMA/CD) and Data Sense Multiple Access with Collision Detection (DSMA/CD). Controlled random access methods include Reservation Aloha, Polling and Token passing schemes.
The fundamental characteristic of random access MAC protocols that limits their achievable throughput is the high incidence of packet collisions under heavy loads of offered data message traffic. A collision is considered to have occurred when two or more users attempt to access the channel simultaneously. During a collision the channel resources are, in effect, wasted. The maximum achievable throughput for the slotted ALOHA protocol is only about 37% and that of DSMA/CD is about 50%. Controlled random access protocols exercise more control over the access method and as a result avoid some of the inefficiencies of the pure random access schemes.
An exemplary prior art multiple access system is presented below to demonstrate some of the key issues addressed by the present invention collision avoidance system. The prior art DSMA/CD system is loosely based on the DSMA/CD scheme by CDPD (cellular digital packet data). The DSMA/CD system consists of a base station and a number of remote units. The base station receives data messages from the remote units on one shared channel. The base station transmits information about the shared channel to the remote units on a different channel. The remote units can only listen on the channel on which the base transmits. They cannot listen to the channel on which they themselves transmit. The information transmitted by the base station consists of two bits of information. The Busy/Idle bit informs the remote units if the shared channel is in use by one of the remote units already. The Decode Status bit informs the remote unit if a data message, transmitted on the shared channel, has been successfully received by a base station. The process of accessing the channel by the remote units is known as arbitration.
If a remote unit has a data message to transmit, it looks at the Busy/Idle bit it receives from the base station. If the shared channel is busy, then the remote unit waits until the received Busy/Idle bit indicates that the shared channel is idle. Once the shared channel is idle, the remote unit can begin its transmission of the data message on the channel. It continues to sense the Busy/Idle bit after it has begun its transmission. If the remote unit is the only one that has accessed the channel, then the Busy/Idle bit will be set to busy after the duration of a round-trip delay between the base station and the remote unit. This round-trip delay includes the propagation time for the transmissions between the remote station and the base unit, as well as any processing of the data by the base station and the remote unit.
If the base station successfully receives the data message transmissions from the remote unit, then it indicates that the remote unit has successfully accessed the channel by setting the Busy/Idle flag to busy. The remote unit will see the busy indication after a round-trip delay and will continue data message transmission until it is done. The maximum amount of time the remote unit is allowed to transmit is usually fixed as a system design parameter.
If, however, a second remote unit has a data message to transmit at the same time as the first remote unit, then it too will see that the channel is idle, and it too will begin to transmit its data message. In this case, the base station will receive a signal that consists of the superposition of the transmitted data messages from both remote units. The base station detects that more than one remote unit is transmitting simultaneously and in this case keeps the Busy/Idle bit at idle. Both remote units will see the idle indication after a round-trip delay. The fact that the channel has remained idle indicates to both units that they have not successfully accessed the channel and so they cease transmissions immediately. They both delay a random amount of time before attempting to access the channel again. This delay is known as a backoff. The remote units will continue to attempt to transmit their data messages until the data message is successfully transmitted or until the maximum number of allowable backoffs has been reached. If the maximum number of backoffs has been reached, then the data message is simply discarded.
There are many parameters that can be adjusted in the prior art scheme in order to improve the overall performance of the DSMA/CD algorithm. These parameters include the number of backoffs, the size of backoffs, etc. The results shown here are based on the best case performance that has been achieved for the DSMA/CD algorithm. The backoff scheme used is known as exponential backoff, where the amount of time spent waiting between access attempts is randomly chosen between zero and an exponential function of the number of backoffs.
The uplink utilization does not change appreciably as the number of remote units is increased from 5 to 30, as shown in Table 1. However, the utilization is relatively low, at approximately 54%.
Table 1 illustrates the uplink utilization vs. the number of active remote units in a heavily loaded system.
TABLE 1Uplink Utilization vs. Number of active remote unitsNumber ofUplinkRUsUtilization% Discarded554.1% .4%1054.6%1.4%1554.2%3.1%2053.4%4.8%
The uplink utilization does not present the total picture however. The number of discarded frames as a function of the number of remote units must also be examined. In Table 1 it can be seen that the number of discarded frames increases approximately linearly with the number of active RUs on the system. The only way to bring down the number of discards is by increasing the maximum allowable number of backoffs or by increasing the size of the backoffs. However, doing so decreases the latency and throughput for smaller numbers of remote units. The utilization with the DSMA/CD algorithm is at best ˜55%. This means that 45% of the shared channel capacity is being lost.
After a remote unit has finished its data message transmissions, it must attempt once again to gain access to the shared channel. The duration of the access attempt is non-deterministic due to the possibility of collisions on the uplink. The DSMA/CD algorithm toggles between the arbitration period and channel-seized period for each remote unit that wants to access the uplink, which is an inefficient use of the shared channel.
With DSMA/CD the number of frames discarded is a function of the number of active remote units on the system and the maximum number of backoffs. Increasing the maximum number of backoffs reduces the percentage of discarded frames. However, this can lead to an ‘unfair’ sharing of the uplink in the short term. The backoff period increases exponentially with the number of backoffs. While remote unit #1 is backing off multiple times, remote unit #2 may be grabbing the channel between backoffs, in effect blocking remote unit #1 from ever gaining access to the shared channel. Also, multiple backoffs by the MAC layer may lead to backoffs by the upper layers (e.g., FTP), which further exaggerates the unfair sharing of uplink resources.
It would be advantageous if the amount of time spent in arbitration for an uplink channel could be minimized and the amount of time spent transmitting data messages could be maximized.
It would be advantageous if a scheme could be developed that permitted multiple RUs to arbitrate simultaneously, and then be granted an access channel without further arbitration.
It would be advantageous if all RUs had equal access to complete their data message transmissions.
It would be advantageous if a multiple access scheme could be developed which avoided the problem of discarded frames and permitted a more ‘fair’ sharing of the uplink.